BOJ24897 숲 게임

풀이

Sprague-Grundy Theorem에 의해, 그런디 수를 하나 이상 골라서 XOR한 값이 0이 될때만 B가 이길 수 있습니다. 일단, 각 트리의 그런디 수를 계산했다고 가정합시다. basis를 제외한 나머지 벡터(종속 벡터) 집합의 power set을 생각해봅시다.

원소의 합 = 0: 그 자체로 B 승리

그렇지 않은 경우: basis로 덧셈 역원을 만들어서 추가하면 B 승리

종속 벡터 집합의 power set에 대해 모두 0을 만들 수 있으면서, basis가 어떤 수 하나를 표현하는 방법은 유일하기 때문에 전체 경우의 수는 2^(n-|basis|)-1입니다.

트리의 그런디 수를 계산해봅시다. 그런디 수는 ‘가능한 다음 상태들의 그런디 수 집합’의 mex로 정의됩니다. 정점 x와 거리가 k 이하인 정점들의 그런디 수 집합의 mex를 구하면 됩니다. 거리가 k 이하인 그런디 수를 pbds_map[key=grundy,val=cnt] 혹은 세그트리로 저장했다면 이분탐색을 이용해 mex를 O (log^2 N)에 구할 수 있습니다. small to large를 이용해 두 map을 amortized O (log^2 N)에 합칠 수 있습니다. 범위를 벗어나는 정점을 제거하기 위해 우선순위 큐도 관리해야 합니다. 이제 O (N log^2 N) 시간에 문제를 해결할 수 있습니다.

코드: http://boj.kr/c4325a093ac14aeaa19c607775d841b7